/*
 * Copyright (C), 2015-2018
 * FileName: Solution101
 * Author:   zhao
 * Date:     2018/9/9 13:03
 * Description: 101. 对称二叉树
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.TreeNode;
import com.lizhaoblog.hundredone.CommonValue;

import java.util.LinkedList;

/**
 * 〈一句话功能简述〉<br>
 * 〈101. 对称二叉树〉
 *
 * @author zhao
 * @date 2018/9/9 13:03
 * @since 1.0.1
 */
public class Solution101 {
  /**************************************
   * 题目
   给定一个二叉树，检查它是否是镜像对称的。

   例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

   1
   / \
   2   2
   / \ / \
   3  4 4  3
   但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
   1
   / \
   2   2
   \   \
   3    3
   说明:
   如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
   **************************************/

  /**************************************
   *
   * 想法：
   *    使用递归方法
   *    直接使用第100题的解决方案
   * 我的做法
   *    没做出来，失败
   * 总结：
   *  理解错了镜像对称
   *
   * ***********************************/
  public boolean isSymmetric(TreeNode root) {
    if(CommonValue.NOT_ANSWER){
    }

    if (root == null) {
      return true;
    }
    return isSymmetric(root.left, root.right);
  }

  public boolean isSymmetric(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
      return true;
    } else if (p == null || q == null) {
      return false;
    }
    if (p.val == q.val) {
      return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
    }
    return false;
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public boolean better(TreeNode root) {
    if (root == null) {
      return true;
    }
    return isSym(root.left, root.right);
  }

  private boolean isSym(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
      return true;
    }
    if (left == null || right == null) {
      return false;
    }

    if (left.val != right.val) {
      return false;
    }
    return isSym(left.left, right.right) && isSym(left.right, right.left);
  }

  /**
   * 迭代方法 (Iterative Solution)
   *
   * @param root 根节点
   * @return 是否对称
   */
  public boolean better2(TreeNode root) {
    LinkedList<TreeNode> treeNodes = new LinkedList<>();
    if (root == null) {
      return true;
    }
    treeNodes.add(root.left);
    treeNodes.add(root.right);
    while (treeNodes.size() > 1) {
      TreeNode left = treeNodes.poll(), right = treeNodes.poll();
      if (left == null && right == null) {
        continue;
      }
      if (left == null || right == null) {
        return false;
      }

      if (left.val != right.val) {
        return false;
      }
      treeNodes.add(left.left);
      treeNodes.add(right.right);
      treeNodes.add(left.right);
      treeNodes.add(right.left);
    }
    return true;
  }

}
